package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 37. 解数独
 * 编写一个程序，通过填充空格来解决数独问题。
 * <p>
 * 数独的解法需 遵循如下规则：
 * <p>
 * 数字 1-9 在每一行只能出现一次。
 * 数字 1-9 在每一列只能出现一次。
 * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
 * 数独部分空格内已填入了数字，空白格用 '.' 表示。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
 * 输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
 * 解释：输入的数独如上图所示，唯一有效的解决方案如下所示：
 * <p>
 * <p>
 * <p>
 * <p>
 * 提示：
 * <p>
 * board.length == 9
 * board[i].length == 9
 * board[i][j] 是一位数字或者 '.'
 * 题目数据 保证 输入数独仅有一个解
 */
public class SolveSudoku {

    // 第一个是行或列，第二个是数字，值为出现的次数，大于1表示出现两次了
    static boolean[][] rows = new boolean[9][10];
    static boolean[][] cols = new boolean[9][10];
    static boolean[][] cells = new boolean[9][10];
    static List<int[]> emptyList = new ArrayList<>();

    /**
     * TODO 思路没问题 代码有点问题
     *
     * @param board
     */
    public void solveSudoku(char[][] board) {

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                char c = board[i][j];
                int num = c - '0';
                if (c == '.') {
                    emptyList.add(new int[]{i, j});
                } else {
                    rows[i][num] = true;
                    cols[j][num] = true;
                    cells[(i / 3) * 3 + j / 3][num] = true;
                }
            }
        }

        dfs(board, 0);
    }

    // 要把emptyList全部填满，index = emptyList的长度
    public boolean dfs(char[][] board, int index) {
        if (index == emptyList.size()) {
            return true;
        }

        int row = emptyList.get(index)[0];
        int col = emptyList.get(index)[1];

        // row 行 col列目前是空的，从1遍历到9看哪个可以填进去
        for (int num = 1; num <= 9; num++) {

            if (rows[row][num] == true || cols[col][num] == true || cells[(row / 3) * 3 + col / 3][num] == true) {
                continue;
            }


            rows[row][num] = cols[col][num] = cells[(row / 3) * 3 + col / 3][num] = true;
            board[row][col] = (char) num;

            if (dfs(board, num + 1)) {
                return true;
            }

            rows[row][num] = cols[col][num] = cells[(row / 3) * 3 + col / 3][num] = false;
            board[row][col] = '.';
        }

        return false;
    }
}
